class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

class Solution:
    # @param intervals, a list of Interval
    # @return a list of Interval
    def merge(self, intervals):
        if intervals == []:
            return []
        intervals.sort(key=lambda interval: interval.start)
        ans = [intervals[0]]
        for inter in intervals[1:]:
            last = ans[-1]
            if inter.start <= last.end:
                last.end = max(inter.end, last.end)
            else:
                ans.append(inter)
        return ans

if __name__ == '__main__':
	s = Solution()
	t1 = Interval(1,3)
	t2 = Interval(2,7)
	t3 = Interval(8,10)
	t4 = Interval(15,18)
	t5 = Interval(16,17)

	a = [t1,t2,t3,t4,t5]
	x = s.merge(a)

	for xx in x:
		print(xx.start, xx.end)
